package edu.vt.ece.rt.benchmark.bst;

import java.util.ArrayList;
import java.util.Random;

import edu.vt.ece.rt.quorum.Resource;
import org.jgroups.annotations.LocalAddress;

import edu.vt.ece.rt.dstm.Context;
import edu.vt.ece.rt.dstm.ContextDelegator;
import edu.vt.ece.rt.dstm.QObject;
import edu.vt.ece.rt.dstm.TMProxy;
import edu.vt.ece.rt.quorum.ClustersManager;
import edu.vt.ece.rt.quorum.Resource;
import edu.vt.ece.rt.quorum.util.AbortException;
import edu.vt.ece.rt.quorum.util.Names;
import edu.vt.ece.rt.util.Logger.Logger;
import edu.vt.ece.rt.benchmark.BenchmarkThread;
import edu.vt.ece.rt.benchmark.hashmap.Hashmap;
import edu.vt.ece.rt.benchmark.list.List;


public class BST extends QObject{

	int val;
	String left;
	String right;
	String id;
	static boolean first = true;
	static ArrayList<String> leaves = new ArrayList<String>();

	public BST(String id, int v, String left, String right) {
		this.val = v;
		this.left = left;
		this.right = right;
		this.id = id;
		Resource.putQObject(getId(), this);
	}

	public BST() {

	}


	public int getVal() {
		return val;
	}

	public void setVal(int v) {
		val = v;
	}

	public String getLeft() {
		return left;
	}

	public void setLeft(String l) {
		left = l;
	}

	public String getRight() {
		return right;
	}

	public void setRight(String r) {
		right = r;
	}

	@Override
	public String getId() {
		return id;
	}

	public void setId(String id) {
		this.id = id;
	}

	@Override
	public QObject clone() {
		BST b= new BST();
		b.setId(getId());
		b.setVersion(getVersion());
		b.setCloneOwner(getCloneOwner());
		b.setLeft(getLeft());
		b.setRight(getRight());
		b.setVal(getVal());
		return b;
	}

	public void add(int val) {

		String root = "root";
		String currNodeId = root;
		BST bst = null;
		boolean left  = true;

		do {
			System.out.println("curr node is "+currNodeId);
			bst = (BST) Resource.getQObject(currNodeId);
			if (val <= bst.getVal()) {
				currNodeId = bst.getLeft();
				left = true;
			} else {
				left = false;
				currNodeId = bst.getRight();
			}
		} while (currNodeId != null);

		BST newNode = new BST(Integer.toString(val), val, null, null);

		if (left) {
			bst.setLeft(newNode.getId());
		} else {
			bst.setRight(newNode.getId());
		}
	}

	public void createBtree(int start, int end) throws Throwable {

		int mid = (start +  end)/2;
		int lStart = 0, rStart = 0, lEnd = 0, rEnd = 0;
//		System.out.println("Start=" +start);System.out.println("End=" +end);

		if (end == (start + 1)) {
			add(start);
			add(end);
//			System.out.println("Start1=" +start);System.out.println("End1=" +end);
			return;
		} else if (start == end) {
//			System.out.println("start=end" +start);
			add(start);
		} else {
//			System.out.println("Mid=" +mid);
			if (first) {
				new BST("root", mid, null, null);
				first = false;
			} else { 
				add(mid);
			}
			lStart = start;
			lEnd = mid - 1;
			createBtree(lStart, lEnd);
			rStart = mid + 1;
			rEnd = end;
			createBtree(rStart, rEnd);
		}
	}

	public static void findLeaves(String root){

		if (root == null)
			return;

		String currNodeId = root;
		BST bst = null;


		bst = (BST) Resource.getQObject(currNodeId);
		if (bst.getLeft() == null && bst.getRight() == null) {
			leaves.add(bst.getId());
		}
		findLeaves(bst.getLeft());
		findLeaves(bst.getRight());
	}

	public static Boolean find(int val, Context parentContext) {

		Boolean found = null;
		Long priority = System.currentTimeMillis();

		for (int i = 0; i < 0x7fffffff; i++) {
			
			((BenchmarkThread)Thread.currentThread()).collectStatsRoot(i);
			Context context = ContextDelegator.getNestedContext();
			context.setParent(parentContext);
			context.setDescription("find element "+val+" in bucket");
			context.sanityNested();
			context.setPriority(priority);

			Logger.debug("----Started----- R Transaction "+context.getContextId()+" on "+ClustersManager.baseClusterId);
			try {

				String root = "root";
				String currNodeId = root;
				BST bst = null;
				do {
					bst = (BST) TMProxy.getTMProxy().read(currNodeId, context.getContextId());
					Logger.debug("currently at "+bst.getVal());
					if (val <= bst.getVal()) {
						currNodeId = bst.getLeft();
					} else {
						currNodeId = bst.getRight();
					}
				} while (bst.getVal() != val && currNodeId != null);

				if (TMProxy.getTMProxy().requestCommit(context.getContextId())) {
					context.unsetParent(parentContext);
					return found;
				}

			} catch (AbortException e) {
				e.touch();
			}
		}
		Logger.fetal("Unable to complete transaction in given number of tries");

		return found;
	}

	public static String add(int val, Context parentContext) throws AbortException {

		String add = null;

		for (int i = 0; i < 0x7fffffff; i++) {
			
		
			((BenchmarkThread)Thread.currentThread()).collectStatsInner(i);
			Context context = ContextDelegator.getNestedContext();
			context.setParent(parentContext);
			context.setDescription("add element "+ val +" in bucket");
			context.sanityNested();

			Logger.debug("----Started----- R Transaction "+context.getContextId()+" on "+ClustersManager.baseClusterId);
			try {
				addWork(val , context);
				
				context.mergeParent();
				return add;
				
			} catch (AbortException e) {	
				if (e.getTransaction().longValue() != context.getContextId().longValue()) {
					Logger.debug("Exception in parent transaction "+e.getTransaction());
					throw e;
				} else {
					Logger.debug("Exception in current transaction "+e.getTransaction());
				}
			}
		}
	
		return add;
	}

	/* send val such that only leaves are deleted */
	public static Boolean delete(int val, Context parentContext) throws AbortException {
//
		Boolean delete = null;

		for (int i = 0; i < 0x7fffffff; i++) {
			
			((BenchmarkThread)Thread.currentThread()).collectStatsInner(i);

			Context context = ContextDelegator.getNestedContext();
			context.setParent(parentContext);
			context.setDescription("delete element "+ val +" in bucket");
			context.sanityNested();

			Logger.debug("----Started----- R Transaction "+context.getContextId()+" on "+ClustersManager.baseClusterId);
			try {

				deleteWork(val, context);
				
				context.mergeParent();
				return delete;


			} catch (AbortException e) {			
				if (e.getTransaction().longValue() != context.getContextId().longValue()) {
					Logger.debug("Exception in parent transaction "+e.getTransaction());
					throw e;
				} else {
					Logger.debug("Exception in current transaction "+e.getTransaction());
				}
			}
		}
		return false;
	}


	public static void addWork(int val, Context context) throws AbortException{
		String root = "root";
		String currNodeId = root;
		BST bst = null;
		boolean left = true;
		String add;
		do {
			bst = (BST) TMProxy.getTMProxy().read(currNodeId, context.getContextId());
			if (val <= bst.getVal()) {
				currNodeId = bst.getLeft();
				left = true;
			} else {
				left = false;
				currNodeId = bst.getRight();
			}
		} while (bst.getVal() != val && currNodeId != null);

		if (currNodeId == null) {
			Context dummy = ContextDelegator.getNestedContext();
			String id = Long.toString(dummy.getContextId());
			BST b = new BST();
			b.setId(id);
			b.setVal(val);
			b.setLeft(null);
			b.setRight(null);
			context.addToCreateSet(b);
			bst = (BST) TMProxy.getTMProxy().write(bst.getId(), context.getContextId());
			if (left) {
				bst.setLeft(b.getId());
			} else {
				bst.setRight(b.getId());
			}
			add = b.getId();
		}
		
	}

	public static void deleteWork(int val, Context context) throws AbortException{
		
		BST parent = null;
		boolean left = true;
		String currNodeId = "root";
		
		BST bst = null;

		do {
			parent = bst;
			bst = (BST) TMProxy.getTMProxy().read(currNodeId, context.getContextId());
			if (val <= bst.getVal()) {
				currNodeId = bst.getLeft();
				left = true;
			} else {
				left = true;
				currNodeId = bst.getRight();
			}
		} while (bst.getVal() != val && currNodeId!=null);

		// only delete leaf nodes
		if (parent != null && bst.getLeft() == null && bst.getRight() == null) {
			parent = (BST) TMProxy.getTMProxy().write(parent.getId(), context.getContextId());
			
			if (parent.getLeft() != null && parent.getLeft().equals(bst.getId())) {
				parent.setLeft(null);
			} else {
				parent.setRight(null);				
			}
		}

	}

	public static void closedNested(int localObjectsCount) {
		
		Random random = new Random();
		Context parentContext = null;
		Long priority = System.currentTimeMillis();

		for (int i = 0; i < 0x7fffffff; i++) {
			
			((BenchmarkThread)Thread.currentThread()).collectStatsRoot(i);

			Context context = ContextDelegator.getNestedContext();
			context.setParent(parentContext);
			context.setDescription("starting root transaction");
			context.sanityNested();
			context.setPriority(priority);

			Logger.debug("----Started----- R Transaction "+context.getContextId()+" on "+ClustersManager.baseClusterId);
			try {

				for (int j = 0; j < Integer.getInteger(Names.calls);j++)  {

					int val = random.nextInt(localObjectsCount);
					Boolean delOp = false;

					if (random.nextInt(100) > 50) {
						delOp = true;
					}

					if (delOp) {
						Logger.debug("delete op started on "+ClustersManager.baseClusterId);
//						BST.delete(val, context);
						BST.deleteWork(val, context);
					} else {
//						BST.add(val, context);
						BST.addWork(val, context);
					}
				}

				if (TMProxy.getTMProxy().requestCommit(context.getContextId())) {
					context.unsetParent(parentContext);
					return;
				}

			}  catch (AbortException e) {
				e.touch();
			}
		}

	}




}